package practice_2025_10.practice_10_10;

import practice_2025_9.practice_9_24.TreeNode;

class Solution {
    /**
     * 轮转数组
     * 数组翻转+模拟
     * @param nums
     * @param k
     */
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        // 计算轮转位置
        k = k % n;
        reverse(nums, 0, n - 1);
        // System.out.println(Arrays.toString(nums));
        reverse(nums, 0, k - 1);
        reverse(nums, k, n - 1);
    }
    public void reverse(int[] nums, int l, int r) {
        if (l >= r) {
            return;
        }
        int left = l, right = r;
        while(left <= right) {
            int tmp = nums[left];
            nums[left] = nums[right];
            nums[right] = tmp;
            left++;
            right--;
        }
    }

    int res = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        maxCount(root);
        return res;
    }

    /**
     * 二叉树中的最大路径和
     * 递归
     * @param root
     * @return
     */
    public int maxCount(TreeNode root) {
        if (root == null) {
            return 0;
        }
        // 计算以左子节点为根的最大路径和
        int leftCount = Math.max(maxCount(root.left), 0);
        // 计算以右子节点为根的最大路径和
        int rightCount = Math.max(maxCount(root.right), 0);
        // 计算该节点的最大路径
        int count = root.val + leftCount + rightCount;
        // System.out.println("root: " + count + " leftCount: " + leftCount + " rightCount: " + rightCount);
        res = Math.max(res, count);
        return (root.val + Math.max(leftCount, rightCount));
    }
}